package com.stefan.lru;

/*
* 思路
* 1. 单向链表
* 2. 采用头插法 -> 保证了月薪的数据越靠近头部
* 3. 插入时：判断链表中有没有该元素，没有的话直接插入头部，
* 有的话就把该元素move到head（从链表中删除该元素，然后插入头部）
* 4. 取数据：取数据时候，判断是不是head，如果不是就move到head
* 5. 最后删除超过capacity的链表尾部数据
* */
public class LRUCacheBase<K,V> {
    int capacity;
    int size;
    Node<K,V> head;

    public LRUCacheBase () {
        this.capacity = 10;
        this.size = 0;
        head = null;
    }


    static class Node<K,V> {
        K key;
        V value;
        Node<K,V> next;
        public Node (K key,V value) {
            this.key = key;
            this.value = value;
        }
    }

    public boolean push(K k,V v) {
        isExistAndRemove(k);
        addToHead(k,v);
        //step5 - 淘汰
        delete();
        return true;
    }

    private void addToHead(K k,V v) {
        Node<K,V> node = new Node<>(k,v);
        node.next = head;
        head = node;
        size++;
    }

    //存在删除然后返回删除的value
    private V isExistAndRemove(K k) {
        if (isEmpty()) {
            return null;
        }
        Node<K,V> current = head;
        Node<K,V> prev = head;
        do {
            if (k.equals(current.key)) {
                V var = null;
                if (current == head) {
                    var = head.value;
                    head = head.next; //删除头部 - 通过设置next是新head
                } else {
                    var = current.value;
                    prev.next = current.next;
                }
                size--;
                return var;
            }
            prev = current;
            current = current.next;
        } while (current!=head && current != null);
        return null;
    }

    private boolean isEmpty() {
        return size == 0;
    }

    public V get(K k) {
        //step4
        V existAndRemove = isExistAndRemove(k);
        addToHead(k,existAndRemove);
        return existAndRemove;
    }

    private void delete() {
        if (size > capacity) {
            Node<K,V> var = head;
            for (int i = 1; i < capacity; i++) {
                var = var.next;
            }
            var.next = null; //删除capacity后的数据
            size = capacity; //更新size
        }
    }

    public static void main(String[] args) {
        LRUCacheBase<String,String> lruCacheBase = new LRUCacheBase<>();
        lruCacheBase.push("1","1");
        lruCacheBase.push("2","2");
        lruCacheBase.push("3","3");
        lruCacheBase.push("4","4");
        lruCacheBase.push("5","5");
        lruCacheBase.push("6","6");
        lruCacheBase.push("7","7");
        lruCacheBase.push("8","8");
        lruCacheBase.push("9","9");
        lruCacheBase.push("10","10");
        System.out.println(lruCacheBase.get("1"));
        System.out.println(lruCacheBase.get("2"));
        System.out.println(lruCacheBase.get("3"));
        System.out.println(lruCacheBase.get("4"));
        lruCacheBase.push("11","11");//淘汰5
        lruCacheBase.push("12","12"); //淘汰6
        System.out.println("========");
    }

}
